package _003Circular_List

import (
	"fmt"
)

// 循环链表 :
// 单向链表加了个功能, 就是最后一个元素的 next指向头元素, 在删除尾部元素的时候需要注意一下

// 从任何一个节点开始遍历整个链表

//链表头部, 用一个空节点来表示

type Object interface{}

type Node struct {
	Data Object
	next *Node
}

type CirCleList struct {
	headNode *Node
}

//添加元素
func (this *CirCleList) Add(data Object) {
	new_node := &Node{Data: data}
	if this.headNode == nil {
		this.headNode = new_node
	} else {
		cur := this.headNode
		// 先把cur 运行到尾部
		for cur.next != nil && cur.next != this.headNode {
			cur = cur.next
		}
		new_node.next = this.headNode
		cur.next = new_node
	}
}

func (this *CirCleList) Empty() bool {
	if this.headNode == nil {
		return true
	} else {
		return false
	}
}

func (this *CirCleList) Show() {
	if this.Empty() {
		fmt.Println("链表为空链表")
	}
	cur := this.headNode
	fmt.Printf("\t %v", cur.Data)
	for cur.next != this.headNode {
		// 如果直接打印 cur, 那么最后一个元素永远不会展示出来
		// 所以, 修改成for 循环前打印头元素, for 循环体中打印当前元素的下一个元素
		fmt.Printf("\t %v", cur.next.Data)
		cur = cur.next
	}
}

// 从指定元素开始遍历链表
func (this *CirCleList) ShowFromNode(data Object) {
	if this.Empty() {
		fmt.Println("链表为空链表")
	}
	cur := this.headNode

	//第一步, 找到指定元素
	for cur.next != nil && cur.next != this.headNode {
		if cur.Data == data {
			break
		}
		cur = cur.next
	}

	if cur.Data != data {
		//
		fmt.Println("链表中未查询到您输入的元素, 无法开始遍历")
		return
	}

	// 从cur 的位置开始遍历
	fmt.Printf("\t %v", cur.Data)
	for cur.next.Data != data {
		fmt.Printf("\t %v", cur.next.Data)
		cur = cur.next
	}
}

//删除元素
func (this *CirCleList) RemoveNode(data Object) {
	// 第一步, 查找到Node
	cur := this.headNode
	tail := this.TailNode()
	if cur.Data == data {
		// 删除头结点

		this.headNode = cur.next
		tail.next = cur.next
	} else {
		pre := tail
		for cur.next != this.headNode {
			if cur.Data == data {
				break
			}
			cur = cur.next
			pre = pre.next
		}

		//if cur.next == this.headNode{
		//	// 当前元素是最后一个元素, 当前元素的上一个元素指向  this.headNode
		//	pre.next = this.headNode
		//} else {
		//	pre.next = cur.next
		//}
		// 优化为如下代码
		pre.next = cur.next
	}

}

//查找尾结点
/*
TailNode 获取尾部结点
*/
func (this *CirCleList) TailNode() *Node {
	cur := this.headNode
	for cur.next != this.headNode {
		cur = cur.next
	}
	return cur
}
